/*================================================================
*   文件名称：main.cpp
*   创 建 者：yang qiang
*   创建日期：2020年12月06日
*   描    述：
*   Copyright (C) 2020 All rights reserved.
*   
* ================================================================*/


#include <iostream>
#include <vector>
using namespace std;

class Solution {
private:
    const int UNCOLORED = 0;
    const int RED = 1;
    const int GREEN = 2;
    vector<int> color;
    bool valid = true;
    
public:
    void dfs(vector<vector<int>>& graph, int node_color, int node){
        color[node] = node_color;
        int n_color = node_color==RED?GREEN:RED;
        for(int k = 0; k < graph[node].size(); k++){
            if(color[graph[node][k]] == UNCOLORED){
                dfs(graph, n_color, graph[node][k]);
            } else{
                if(color[graph[node][k]] != n_color){
                    valid = false;
                    return;
                }
            }
        }

        return;
    }

    bool isBipartite(vector<vector<int>>& graph) {
        int m = graph.size();
        if(!m){
            return false;
        }

        color.assign(m, UNCOLORED);

        for(int i = 0; i < m && valid; i++){
            if(color[i] == UNCOLORED){
                dfs(graph, RED, i);
            }
        }

        return valid;
    }
};


int main(){
    vector<vector<int>> graph =  {{3,4,6},{3,6},{3,6},{0,1,2,5},{0,7,8},{3},{0,1,2,7},{4,6},{4},{}};
    Solution s;
    cout << s.isBipartite(graph) << endl;
    for(int i = 0; i < s.color.size(); i++){
        cout << s.color[i]<< " ";
    }
    return 0;
}
